import math


class treenode:
  def _init_(self,data,loader=None,lchild=None,rchild=None):
    self.data=data
    self.loader=loader
    self.lchild=lchild
    self.rchild=rchild
	
def secondoptimal(node,r,sw,l,h):
  if not node:
    node=treenode()
    node.loader=node
    node.lchild=None
    node.rchild=None
  
  i=l;
  dw=sw[h]+sw[l]
  min=abs(sw[h]-sw[l])
  
  for j in range(l+1,h):  
    if abs(dw-sw[j-1]-sw[j])<min:
      i=j
      min=abs(dw-sw[j-1]-sw[j])
    j=j+1
	  
  node.data=r[i]
  
  if i==l:
    node.lchild=None
  else:    
    node.lchild=secondoptimal(node.lchild,r,sw,l,i-1)
	
  if i==h:
    node.rchild=None
  else:
    node.rchild=secondoptimal(node.rchild,r,sw,i+1,h)
	
  return node
	
def preorder_search(order,node):
  if node.data:
    order=order+(node.data,)	
  if node.lchild:
      order=preorder_search(order,node.lchild)
  if node.rchild:
      order=preorder_search(order,node.rchild)  
  return order
	 
def midorder_search(order,node):
  if node.lchild:
    order=midorder_search(order,node.lchild)
  if node.data:
    order=order+(node.data,)
  if node.rchild:
    order=midorder_search(order,node.rchild)
  return order
	
def postorder_search(order,node):
  if node.lchild:
    order=postorder_search(order,node.lchild)
  if node.rchild:
    order=postorder_search(order,node.rchild)
  if node.data:
    order=order+(node.data,)
  return order	

low=1
high=10

t=()
#init the nodes
for i in range(low-1,high-1):
  a=chr(ord('A')+i)
  t=t+(a,)
  
weight=(1,1,2,5,3,4,4,3,5)

w=()
for i in range(low,high):
  sum=weight[0]
  for j in range(low,i):
    sum=sum+weight[j]
  w=w+(sum,)


  
#  startup   
print t
print w

root=None

node1=secondoptimal(root,t,w,low-1,high-2)

od=()
print(preorder_search(od,node1))
print(midorder_search(od,node1))
print(postorder_search(od,node1))


   
